// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

// 寻找最短路径的 Dijkstra 算法
func Dijkstra(graph [][]int, source int, destination int, n int) int {
	// 初始化变量
	dist := make([]int, n)
	visited := make([]bool, n)
	var MAX = math.MaxInt32

	for i := 0; i < n; i++ {
		dist[i] = MAX
		visited[i] = false
	}

	dist[source] = 0

	// 寻找最短路径
	for i := 0; i < n-1; i++ {
		minIndex := findMinVertex(dist, visited, n)
		visited[minIndex] = true

		for j := 0; j < n; j++ {
			if !visited[j] && graph[minIndex][j] != 0 &&
				dist[minIndex] != MAX &&
				dist[minIndex]+graph[minIndex][j] < dist[j] {
				dist[j] = dist[minIndex] + graph[minIndex][j]
			}
		}
	}

	// 返回最短距离
	return dist[destination]
}

// 这个函数接受三个参数：
// - 整数切片“dist”，表示图中源顶点与其他顶点之间的距离。
// - 一个布尔切片“visited”表示一个顶点是否被访问过。
// - 一个整数“n”，表示图中的顶点数。
func findMinVertex(dist []int, visited []bool, n int) int {
	// 将最大可能的整数值初始化为 MAX
	var MAX = math.MaxInt32
	// 将最小距离设置为可能的最大整数值
	min := MAX
	// 将最小距离顶点索引初始化为 -1
	minIndex := -1
	// 遍历所有顶点
	for i := 0; i < n; i++ {
		// 检查顶点是否还没有被访问过并且它的距离小于或等于当前的最小距离
		if visited[i] == false && dist[i] <= min {
			// 将最小距离和索引更新为当前顶点的距离和索引
			min = dist[i]
			minIndex = i
		}
	}
	// 返回最小距离顶点的索引
	return minIndex
}

func main() {
	graph := [][]int{{0, 4, 0, 0},
		{4, 0, 8, 0},
		{0, 8, 0, 7},
		{0, 0, 7, 0},
	}
	fmt.Println("从 1 到 3 的最短距离是", Dijkstra(graph, 0, 1, 3))
}

//$ go run dijkstra.go
//从 1 到 3 的最短距离是 4
